#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

class Solution {
public:
    int gcd(int a, int b) {
        return !a ? b : gcd(b % a, a);
    }

    int countDifferentSubsequenceGCDs(vector<int>& nums) {
        int maxVal = *max_element(nums.begin(), nums.end());
        vector<bool>occured(maxVal + 1, false);  // 在 nums 中的数

        int ans = 0;

        for (int i = 0; i < nums.size(); i++) {
            occured[i] = true;
        }

        for (int i = 1; i <= maxVal; i++) {       // 枚举每个可能的最大公因数
            int gcd_res = 0;
            for (int j = i; j <= maxVal; j += i) { // 如果某个 i 的倍数序列确实以 i 为最大公因数，则 ans++
                if (occured[j]) {
                    gcd_res = gcd(gcd_res, j);
                    if (gcd_res == i) {
                        ans++;
                        break;
                    }
                }               
            }
        }
        return ans;
    }
};

int main() {
    return 0;
}

/**
 * 2023.1.14
 * 要求所有序列的不同的最大公因数目，可以枚举所有可能的最大公因数，只要确认有以该数为最
 * 大公因数的序列，那么答案就 + 1,寻找该序列，只需要枚举该数的倍数，首先确认倍数 j 在
 * 数组中，其次确定存在序列以该数为最大公因数（而不是该数的倍数）即可。
*/